МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра САПР Звіт до Лабораторної роботи №3 на тему: «ФОРМАЛЬНІ ГРАМАТИКИ. ЗВ'ЯЗОК ФОРМАЛЬНИХ ГРАМАТИК І СКІНЧЕННИХ АВТОМАТІВ» З курсу «Лінгвістичне забезпечення САПР»  1. МЕТА РОБОТИ Ознайомлення з правилами побудови і застосування автоматів з магазинною пам’яттю. 2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Скінченні автомати можуть вирішувати тільки ті задачі, які потребують скінченного об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних виразів виникає задача перевірки балансу дужок, кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має «свою роль», тому використання скінченного автомата для таких задач не прийнятне, оскільки множина станів може бути нескінченною. Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам'ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазину (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна поміщати в магазин і видаляти їх з нього по одному. При цьому видаляється завжди тільки верхній символ, тобто символ, який був поміщений у магазин останнім. Коли інформація поміщається (записується) в магазин, кажуть, що вона «заштовхується», коли інформація видаляється з магазину – «виштовхується» з нього. Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (скорочено МП-автомат). У ньому дуже просто поєднується пам'ять скінченного автомата і магазинна пам'ять. Як і у випадку скінченного автомата, обробка скінченного ланцюжка символів здійснюється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам’яті може змінюватись за рахунок: а) переходу у новий стан; б) заштовхування символу у магазин; в) виштовхування символу з магазину. Кожний крок обробки задається множиною правил, які використовують інформацію трьох видів: Стан; Верхній символ магазина; Біжучий вхідний символ. Залежно від отриманої інформації керуючий пристрій обирає або перехід в новий стан, або вихід з процесу. Перехід складається з трьох типів операцій: над станом, над магазином і над входом. Можливі такі операції: 1. Операції над магазином: Заштовхнути в магазин відповідний символ; Виштовхнути верхній символ з магазину; Залишити магазин без змін. 2. Операції над станом: Перейти в заданий стан. 3. Операції над входом: Перейти до наступного вхідного символу і зробити його поточним; Залишити цей вхідний символ поточним. МП-автомат визначається такими характеристиками:
де
– скінченна множина символів станів, які відображають усі можливі стани керуючого пристрою;
- скінченний вхідний алфавіт;
- скінченний алфавіт магазинних символів;
- керуюча функція, яка кожній комбінації вхідного символу, магазинного символу, стану ставить у відповідність перехід у відповідний стан або вихід;
- початковий стан керуючого пристрою;
- початковий символ, який є в магазині в початковий момент;
- множина прикінцевих станів. МП-автомат називається розпізнавачем, якщо у нього є два виходи: 1. ДОПУСТИТИ; 2. ВІДКИНУТИ. Ланцюжок символів вхідного алфавіту (включаючи кінцевий маркер) допускається розпізнавачем, якщо під дією цього ланцюжка автомат, який розпочав роботу у своєму початковому стані з початковим вмістом магазина, робить ряд переходів, які приводять до виходу «ДОПУСТИТИ». В протилежному випадку ланцюжок відкидається. При описанні переходів МП-автомата позначатимемо дії автомата словами: ЗАШТОВХНУТИ (А) – заштовхнути магазинний символ А у магазин; ВИШТОВХНУТИ – виштовхнути верхній символ з магазина; СТАН (S) – стан S; ЗСУВ – зсунути вхідну головку на один символ; ТРИМАТИ – тримати поточний вхідний символ до наступного кроку. 3. ВИКОНАННЯ РОБОТИ ІНДИВІДУАЛЬНЕ З...